package org.example.sward.tooffer;

public class IsMatch {

    public boolean isMatch(String s, String p) {
        int m = s.length(),n = p.length() ;
        //定义一个boolean数组记录是否匹配正则表达式
        boolean[][] dp = new boolean[m+1][n+1];
        dp[0][0] = true;
        //初始化,匹配空字符串
        for (int i = 2; i <= n; i++) {
            if(p.charAt(i-1) == '*'){
                dp[0][i] = dp[0][i-2];
            }
        }

        for (int i = 1; i <=m; i++) {
            for (int j = 1; j <=n ; j++) {
                char sc = s.charAt(i-1);
                char pc = p.charAt(j-1);
                if(pc == '*'){
                    if(dp[i][j-2]){
                        dp[i][j] = true;
                    }else if(sc == p.charAt(j-2) || p.charAt(j-2) == '.'){
                        dp[i][j] = dp[i-1][j];
                    }
                }else if(sc == pc || pc== '.'){
                   dp[i][j] = true;
                }
            }
        }
        return dp[m][n];


    }

    public boolean solution1(String s, String p){
        if(p.length() == 0){
            return s.length() == 0;
        }

        boolean firstMatch = p.length()>0 && (s.charAt(0) == p.charAt(0)||p.charAt(0) == '.');

        if(p.length() >= 2 && p.charAt(1) == '*'){
            return isMatch(s,p.substring(2)) || (firstMatch && isMatch(s.substring(1),p));
        }else{
            return firstMatch && isMatch(s.substring(1),p.substring(1));
        }
    }

    public static void main(String[] args) {
        IsMatch isMatch = new IsMatch();
        boolean result = isMatch.solution1("aa1","a*");
        System.out.println(result);

    }
}
